package tree.test105;

import listbyorder.utils.TreeNode;

import java.util.HashMap;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/16 12:12
 */
public class Solution1 {

    // DFS
    HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) return null;
        int n = preorder.length;
        for (int i = 0; i < n; i++) {
            map.put(inorder[i], i);
        }
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode dfs(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
        if (pl > pr) return null;
        int c = preorder[pl];
        int k = map.get(c);
        TreeNode root = new TreeNode(c);
        root.left = dfs(preorder, inorder, pl + 1, pl + k - il, il, k - 1);
        root.right = dfs(preorder, inorder, pl + k - il + 1, pr, k + 1, ir);
        return root;
    }
}
